package com.example.demo.leetcode.top;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
 *
 * 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
 *
 * 示例 1：
 *
 * 输入：nums = [1,2,3]
 * 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
 * 示例 2：
 *
 * 输入：nums = [0]
 * 输出：[[],[0]]
 *
 */
public class Array_子集 {

    static List<List<Integer>> resultList = new ArrayList<List<Integer>>();
    public static List<List<Integer>> subsets(int[] nums) {

        //递归解法
        //假定初始集合为空, 每次递归前，复制数组中的所有集合，加入新的元素，然后塞回大集合中
        List<Integer> list = new ArrayList<>();
        for(int i=0;i<nums.length;i++){
            list.add(nums[i]);
        }
        resultList.add(new ArrayList<>());
        digui(list);
        return resultList;
    }

    public static void digui(List<Integer> list){
        if(list.isEmpty()){
            return;
        }
        Integer remove = list.remove(0);
        //假定初始集合为空, 每次递归前，复制大集合中的所有集合，加入新的元素，然后塞回大集合中
        int size = resultList.size();
        for(int i =0;i<size;i++){
            List<Integer> newList = new ArrayList<>(resultList.get(i));
            newList.add(remove);
            resultList.add(newList);
        }
        digui(list);
    }

    public static void main(String[] args) {
        int [] arr = {0};
        List<List<Integer>> subsets = subsets(arr);
        System.out.println(subsets.size());
    }


}
